package org.example;

public class Test2 {
    public int countSubstrings(String s) {
        char[] arr = s.toCharArray();
        int n = arr.length;
        //dp[i][j]表示i-j之间的子串是否为回文子串
        boolean[][] dp = new boolean[n+1][n+1];
        int ret = n;
        for (int i = 0; i <= n; i++) dp[i][i] = true;
        for (int j = 1; j <= n; j++) {
            for (int i = 1; i < j; i++) {
                //当arr[i+1] == arr[j-1]的时候，如果i+1==j，那么就说明由两个字符组成的字符串是回文串
                //如果i+1<j，那么就需要判断[i+1,j-1]的子串是否为回文串了
                if (arr[i-1] == arr[j-1]) dp[i][j] = i+1 > j-1 ? true : dp[i+1][j-1];
                if (dp[i][j]) ret++;
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        Test2 test2 = new Test2();
        test2.countSubstrings("aaa");
        System.out.println(777);
    }
}
